import java.util.Stack;

public class Sort {
	/**
	 * 时间复杂度：最好的情况下是O(N) 最坏的情况下O(N^2)
	 * 空间复杂度：O(1)
	 * 稳定性：稳定
	 * 稳定的排序可以变成不稳定的排序，但是不稳定的排序不能变成稳定的排序
	 * 稳定性指的是原来的顺序不进行改变
	 * @param array
	 */
	public static void insertSort(int[] array) {
		for(int i=1;i<array.length;i++) {
			int tmp=array[i];
			int j=i-1;
			for(;j>=0;j--) {
				if(array[j]>tmp) {
					array[j+1]=array[j];
				} else {
					break;
					//这里直接break是因为直接插入排序的话，前面已经有序了，不满足条件的话直接返回。
				}
			}
			array[j+1]=tmp;
		}
	}

	/**
	 * 时间复杂度：N^1.3  ~  N^1.8
	 * 空间复杂度：O(1)
	 * i无论怎么是i++还是i+=gap，最后直接会变成直接插入排序
	 * 不稳定排序
	 * @param array
	 */
	public static void shellSort(int[] array) {
		int gap=array.length;
		while(gap>1) {
			gap=gap/2;
			shell(array,gap);
		}
	}
	private static void shell(int[] array,int gap) {
		for(int i=gap;i<array.length;i++) {
			int tmp=array[i];
			int j=i-gap;
			for(;j>=0;j-=gap) {
				if(array[j]>tmp) {
					array[j+gap]=array[j];
				} else {
					break;
				}
			}
			array[j+gap]=tmp;
		}
	}

	/**
	 * 时间复杂度：O(N^2)
	 * 空间复杂度：O(1);
	 * 不稳定排序
	 * @param array
	 */
	public static void selectSort(int[] array) {
		for(int i = 0 ; i<array.length;i++) {
			int mindex=i;
			//这里得让j从i+1开始
			for(int j =i+1;j<array.length;j++) {
				if(array[j]>array[mindex]) {
					mindex=j;
				}
			}
			swap(array,i,mindex);
		}
	}
	private static void swap(int[] array,int i,int j) {
		int temp=array[i];
		array[i]=array[j];
		array[j]=temp;
	}

	/**
	 * 在选择排序的基础上进行优化，一次可以找到最大值与最小值
	 * 注意在交换的时候如果maxindex==left，此时进行小的交换的时候把最大值给交换走了
	 * 我们需要重新找到最大值的下标，所以maxindex=minindex。
	 * @param array
	 */
	public static void selectSort1(int[] array) {
		//每次都能找到最大值和最小值
		int left=0;
		int right=array.length-1;
		while(left<right) {
			int minindex=left;
			int maxindex=right;
			for(int i =left+1;i<=right;i++) {
				if(array[i]<array[minindex]) {
					minindex=i;
				}
				if(array[i]>array[maxindex]) {
					maxindex=i;
				}
			}
			swap(array,left,minindex);
			if(maxindex==left)
			{
				maxindex=minindex;
			}
			swap(array,right,maxindex);
			left++;
			right--;
		}
	}

	/**
	 * 时间复杂度：O(N^2)
	 * 空间复杂度：O(1)
	 * 不稳定性排序
	 * @param array
	 */
	public static void bubbleSort(int[] array) {
		for(int i=0;i<array.length;i++) {
			boolean flg=true;
			for(int j =i;j<array.length-1-i;j++) {
				if(array[j+1]>array[j] ) {
					swap(array,j+1,j);
					flg=false;
				}
			}
			if(flg) {
				break;
			}
		}
	}

	/**
	 * 堆排序的时候首先进行建堆，然后再进行排序
	 * 时间复杂度为：N*LogN
	 * 空间复杂度为O(1);
	 * 不稳定的排序
	 *
	 * 向下调整建堆，时间复杂度为，O(N) 并不是循坏几次，
	 * 每层节点数，乘以每层节点数需要向下调整的高度，最后可以根据等比数列求出来时间复杂度。
	 * @param array
	 */
	public static void heapSort(int[] array) {
		createBigHeap(array);
		int end=array.length-1;
		while(end>0) {
			swap(array,0,end);
			siftDown(array,0,end);
			end--;
		}
	}
	private static void createBigHeap(int[] array) {
		for(int parent=(array.length-1-1)/2;parent>=0;parent--) {
			siftDown(array,parent,array.length);
		}
	}
	private static void siftDown(int[] array,int parent,int end) {
		int child=parent*2+1;
		while(child<end) {
			if(child+1<end&&array[child+1]>array[child]) {
				child++;
			}
			if(array[child]>array[parent]) {
				swap(array,parent,child);
				parent=child;
				child=parent*2+1;
			} else {
				break;
			}
		}
	}
	//时间复杂度还得再听

	/**
	 * 时间复杂度：
	 * 最好：N*logN 完全二叉树或者是满二叉树
	 * 最坏：N^2  单分支树
	 * @param array
	 */
	public static void quickSortHore(int[] array) {
		quick(array,0,array.length-1);
	}
	private static void quick(int [ ] array,int start,int end) {
		if(start>=end) {
			return ;
		}
//		if(end-start<100) {
//			insertSortRange(array,start,end);
//			return ;
//		}
//		int index=getMidThree(array,start,end);
//		swap(array,index,start);
		//我们将中间的数据交换到左边，因为key=array[left]
		int privot= parition(array,start,end);
		quick(array,start,privot-1);
		quick(array,privot+1,end);
	}

	private static void insertSortRange(int[] array, int start, int end) {
		for(int i=start;i<=end;i++) {
			int tmp=array[i];
			int j=i-1;
			for(;j>=0;j--) {
				if(array[j]>tmp) {
					array[j+1]=array[j];
				} else {
					break;
				}
			}
			array[j+1]=tmp;
		}
	}

	//霍尔的版本
	private static int parition1(int [] array,int left,int right) {
		int key=array[left];
		int index=left;
		while(left<right) {
			while(left<right&&array[right]>=key){//这里为什么要写等号，还有为什么right先走
				right--;
			}
			while(left<right&&array[left]<=key) {
				left++;
			}
			swap(array,left,right);
		}
		swap(array,index,left);
		return left;
	}

	/**
	 * 挖坑法的快速排序
	 * @param array
	 */
	public static void quickSort(int [] array) {

		quick(array,0,array.length-1);
	}
	//挖坑法
	private static int parition(int [] array,int left,int right) {
		int key=array[left];
		while(left<right) {
			//这里之所以写引号，是因为数组中都是等于key的数据，不带等号的话，变成死循环了
			//前面加left<right是因为，right遇到一路比它大的或者是left遇到一路比它小的，此时会造成数组越界。
			while(left<right&&array[right]>=key) {
				right--;
			}
			//下标一定是比key小的数据，小的数据去左边，直接进行覆盖，覆盖完，right不动了，
			//到下一轮的时候，right处的数据比key小，然后将这个数据又被覆盖，不会造成一个数字出现两次
			array[left]=array[right];
			while(left<right&&array[left]<=key) {
				left++;
			}
			array[right]=array[left];
		}
		array[left]=key;
		return left;
	}
	private static int getMidThree(int[] array, int left, int right) {
		int mid=(right-left)/2;
		if(array[right]>array[left]) {
			if(array[mid]>array[right] ) {
				return right;
			} else if(array[mid]<array[left]) {
				return left;
			} else {
				return mid;
			}
		} else {
			if(array[mid]>array[left]) {
				return left;
			} else if(array[mid]<array[right]) {
				return right;
			} else {
				return mid;
			}
		}
	}
	public static int  parition2(int [] array,int left,int right) {
		//双指针的办法
		int prev=left;
		int cur=left+1;
		while(cur<=right) {
			//刚开始的时候这两个指针是一起走的，直到遇到大的，后面的条件不会进行判断了直接短路
			// 然后cur开始独自往走，然后又遇到小的，prev又开始往前走了。
			if(array[cur]<array[left]&&array[++prev]!=array[cur]) {
				swap(array,prev,cur);
			}
			cur++;
		}
		swap(array,left,prev);
		return prev;
	}
	public static void quickSortNor(int [] array) {

		Stack<Integer> st1=new Stack<>();
		int left=0;
		int right=array.length-1;
		int privot=parition(array,left,right);
		if(privot-1>left) {
			//防止数据全部比left处的数据大，如果这样会造成privot数组越界
			st1.push(left);
			st1.push(privot-1);
		}
		if(privot+1<right) {
			st1.push(privot+1);
			st1.push(right);
		}
		while(!st1.empty()) {
			right=st1.pop();
			left=st1.pop();
			privot=parition(array,left,right);
			if(privot-1>left) {
				st1.push(left);
				st1.push(privot-1);
			}
			if(privot+1<right) {
				st1.push(privot+1);
				st1.push(right);
			}
		}
	}

	/**
	 * 时间复杂度：N*logN
	 * 空间复杂度：N
	 * 稳定排序
	 *
	 * 归并排序后面文件输入以及输出的时候，对文件进行排序需要用到归并排序
	 *
	 * @param array
	 */
	public static void mergeSort(int[] array) {

		mergeSortFunc(array,0,array.length-1);
	}
	private static void mergeSortFunc(int[] array,int left,int right) {
		//这要进行递归
		if(left>=right) {
			return ;
		}
		//一般涉及数组的递归的时候，这个条件必须得加上，是为了防止有一边没有数据，同时left==right是结束条件
		int mid=(right+left)/2;
		mergeSortFunc(array,left,mid);
		mergeSortFunc(array,mid+1,right);
		merge(array,left,right,mid);
	}
	private static void merge(int[] array, int left, int right, int mid) {
		int s1=left;
		int s2=mid+1;
		int k=0;
		int[] tempArr=new int [right-left+1];
		//先进行小的尾插
		//判断其中数组是否为空
		//然后将数据拷贝回原数组
		while(s1<=mid&&s2<=right) {
			if(array[s1]<=array[s2]) {
				tempArr[k++]=array[s1++];
			}
			else {
				tempArr[k++]=array[s2++];
			}
		}
		while(s1<=mid) {
			tempArr[k++]=array[s1++];
		}
		while(s2<=right) {
			tempArr[k++]=array[s2++];
		}
		//拷贝回原数组
		for(int i=0;i<tempArr.length;i++) {
			array[left+i]=tempArr[i];
		}
	}
	//归并排序的非递归
	public static void mergeSortNor(int[] array) {
		int gap=1;
		while(gap<array.length) {
			for(int i=0;i<array.length;i+=2*gap) {
				int left=i;
				int mid=left+gap-1;
				int right=mid+gap;
				if(mid>=array.length) {
					mid = array.length - 1;
				}
				if(right>=array.length) {
					right=array.length-1;
				}
				merge(array,left,right,mid);
			}
			gap*=2;
		}
	}

	/**
	 * 记数排序，统计一个数字出现的次数，比较适用于数据比较集中
	 * 利用最大值和最小值来构造count数组的大小
	 * 时间复杂度：N+范围
	 * 空间复杂度：范围
	 * @param array
	 */
	public static void countSort(int[] array) {
		int minval=array[0];
		int maxval=array[0];
		for(int i=1;i<array.length;i++) {
			if(minval>array[i]) {
				minval=array[i];
			}
			if(maxval<array[i]) {
				maxval=array[i];
			}
		}
		int [] count=new int [maxval-minval+1];
		for (int i = 0; i < array.length ; i++) {
			count[array[i]-minval]++;
		}
		int index=0;
		for (int i = 0; i < count.length;i++) {
			while(count[i]>0) {
				array[index]=i+minval;
				index++;
				count[i]--;
			}
		}
	}
	//还得补充，队列数组
	//思路：先得到最大数的位数，然后创建数组
	//先比较个位数，然后依次出队，之后就是依次比较，每位上数
}
